package priority;

import java.util.PriorityQueue;

/**
 * 295、数据流中的中位数
 */
public class Day19 {
    // 1、创建大根堆(用于有序数组的中值的左面)、小根堆(用于有序数组的中值的右面)
    PriorityQueue<Integer> left; // 大根堆，堆顶就是左面的最大值
    PriorityQueue<Integer> right; // 小根堆，堆顶就是右面的最小值

    public void MedianFinder() {
        // 2、对于堆进行初始化
        left = new PriorityQueue<>((a,b) -> b - a);
        right = new PriorityQueue<>((a, b) -> a - b);
    }

    public void addNum(int num) {
        // 添加数据分成两个规则
        // 1、left.size() == right.size()
        // 2、left.size() == right.size() + 1

        if(left.size() == right.size()) {
            // 1、left.size() == right.size()
            if(left.isEmpty() || num <= left.peek()) {
                // 把num放入到 左面
                // 这个时候 就是 left.size() == right.size() + 1，不违规
                left.offer(num);
            }else {
                // num > left.poll()
                // 这个时候往右面right 中放入，但是放完后就是：left.size()  + 1 == right.size() 不符合规则
                // 所以放入后，要把right那面的最小值放入到left中，变为 left.size() == right.size()
                right.offer(num);
                left.offer(right.poll());
            }
        }else {
            // 2、left.size() == right.size() + 1
            if(num <= left.peek()) {
                // 放入到左面left，但是放完之后呢 就是 left.size() == right.size() + 2，不符合规则
                // 所以当放入后，要把left的一个放入到右面right中，就是left的最左面的堆顶
                left.offer(num);
                right.offer(left.poll());
            }else {
                // 所以当放入后，就是left.size() == right.size()
                right.offer(num);
            }
        }
    }

    public double findMedian() {
        if(left.size() == right.size()) {
            // 这里不能使用poll，只能使用peek因为这个寻找中值会调用多次，并且比较的中值是所有的数据的中值
            return (left.peek() + right.peek()) / 2.0;
        }else {
            // left.size() == right.size() + 1，中值就是left的堆顶
            return left.peek();
        }
    }
}
